#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "sort.h"
#define T 5

static double *a, *merge, *insertion, *shell, *quick, *bubble, *bucket;
static int N[4] = {10, 1000, 10000, 100000};
static double run_time[T][3][6]; /* 5 times * 3 lens * 6 alogorithms */

void get_array(int len)
{
  int i;
  a = (double *)malloc(sizeof(double) * len);
  merge = (double *)malloc(sizeof(double) * len);
  insertion = (double *)malloc(sizeof(double) * len);
  shell = (double *)malloc(sizeof(double) * len);
  quick = (double *)malloc(sizeof(double) * len);
  bubble = (double *)malloc(sizeof(double) * len);
  bucket = (double *)malloc(sizeof(double) * len);
  for (i = 0; i < len; i++) 
    a[i] = merge[i] = insertion[i] = shell[i] = quick[i] = bubble[i] = bucket[i] =  rand() * 1.0 / RAND_MAX;
}

void print_array(double *a, int len)
{
  int i;
  for (i = 0; i < len; i++)
    printf("a[%d] = %f\n", i, a[i]);
}

void get_time(int n)
{
  int i, len;
  clock_t start, finish;

  for (i = 1; i < 4; i++) {
    len = N[i];
    get_array(len);
    printf("\nWhen N=%d, with the same sample a[%d]:\n", len, len);
    printf("The running time of each algorithm is:\n");

    start = clock();
    merge_sort(merge, 0, len - 1);
    finish = clock();
    printf("running time of merge_sort: %f seconds\n", run_time[n][i][0] = (double)(finish - start) / CLOCKS_PER_SEC);

    start = clock();
    insertion_sort(insertion, len);
    finish = clock();
    printf("running time of insertion_sort: %f seconds\n", run_time[n][i][1] = (double)(finish - start) / CLOCKS_PER_SEC);

    start = clock();
    shell_sort(shell, len);
    finish = clock();
    printf("running time of shell_sort: %f seconds\n", run_time[n][i][2] = (double)(finish - start) / CLOCKS_PER_SEC);

    start = clock();
    quick_sort(quick, 0, len - 1);
    finish = clock();
    printf("running time of quick_sort: %f seconds\n", run_time[n][i][3] = (double)(finish - start) / CLOCKS_PER_SEC);

    start = clock();
    bubble_sort(bubble, len);
    finish = clock();
    printf("running time of bubble_sort: %f seconds\n", run_time[n][i][4] = (double)(finish - start) / CLOCKS_PER_SEC);

    start = clock();
    bucket_sort(bucket, len);
    finish = clock();
    printf("running time of bucket_sort: %f seconds\n", run_time[n][i][5] = (double)(finish - start) / CLOCKS_PER_SEC);

    free(a); free(merge); free(insertion); free(shell); free(quick); free(bubble); free(bucket);
  }
}

double average(j, k)
{
  int i;
  double ave = 0;

  for (i = 0; i < T; i++)
    ave += run_time[i][j][k];
  return ave / T;
}

int main()
{
  int i, j, len;

  /* sort a[10] */
  len = N[0];
  get_array(len);
  printf("randomly generated a[%d]:\n", len);
  print_array(a, len);

  printf("\nsort with merge_sort:\n");
  merge_sort(merge, 0, len - 1);
  print_array(merge, len);

  printf("\nsort with insertion_sort:\n");
  insertion_sort(insertion, len);
  print_array(insertion, len);

  printf("\nsort with shell_sort:\n");
  shell_sort(shell, len);
  print_array(shell, len);

  printf("\nsort with quick_sort:\n");
  quick_sort(quick, 0, len - 1);
  print_array(quick, len);

  printf("\nsort with bubble_sort:\n");
  bubble_sort(bubble, len);
  print_array(bubble, len);

  printf("\nsort with bucket_sort:\n");
  bucket_sort(bucket, len);
  print_array(bucket, len);

  free(a); free(merge); free(insertion); free(shell); free(quick); free(bubble); free(bucket);
  printf("-------------end of question(1)-----------------------------------------\n");


  /* for N = 1000, 10000, 100000, get the running time of each algorithm */
  get_time(0);

  printf("-------------end of question(2)-----------------------------------------\n");


  /* 5 times of average */
  for (i = 0; i < 4; i++)
    for (j = 0; j < 6; j++) 
      run_time[0][i][j] = 0;
  for (i = 0; i < T; i++) {
    printf("\n************************time %d*************************", i + 1);
    get_time(i);
  }
  printf("\nConclusion:");
  for (len = 1; len < 4; len++) {
    printf("\nWhen N=%d, the average running time of each algorithms is:\n", N[len]);
    printf("The average running time of merge_sort is: %f seconds\n", average(len, 0));
    printf("The average running time of insertion_sort is: %f seconds\n", average(len, 1));
    printf("The average running time of shell_sort is: %f seconds\n", average(len, 2));
    printf("The average running time of quick_sort is: %f seconds\n", average(len, 3));
    printf("The average running time of bubble_sort is: %f seconds\n", average(len, 4));
    printf("The average running time of bucket_sort is: %f seconds\n", average(len, 5));
  }
  printf("-------------end of question(3)-----------------------------------------\n");
}

